#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
/*
//2407:书架	
int N,res=0,H[20005];
long long S,B;
priority_queue<int> prq;
*/

/*
	//1455:An Easy Problem
//返回x的二进制表示数中1的数量
int numof1(int x){
	int res=0;
	while(x){
		if(x%2==1){
			res++;
		}
		x/=2;
	}
	return res;
}
*/

/*
int n,money,l1,l2,r1,r2;
int a[1005],b[1005];
*/

/*
struct Node{
	int start,end;
	bool operator<(const Node &a) const{
		return end<a.end;
	}
};
Node node[105];
*/


/*
#define MAXN 30
struct Node{
	int f,d,id;
	bool operator<(const Node &a)const{
		if (f==a.f) return id>a.id;
		else return f<a.f;
	}
};
Node a[MAXN];
int temp[MAXN],best[MAXN],dis[MAXN];
int t,n;
priority_queue<Node> pq;
*/

/*
bool operator<(const lake &a,const lake &b) {
	if(a.f==b.f) return a.id>b.id;
	else return a.f<b.f;
}
*/


/*
struct Cow{
	int start,end;
	int No;
	bool operator<(const Cow &a)const{
		return start<a.start;
	}
};
Cow cows[MAXN];
int pos[MAXN];
struct Stall{
	int end,No;
	bool operator<(const Stall &a)const{
		return end>a.end;
	}
	Stall(int e,int n):end(e),No(n){
	}
};
priority_queue<Stall> pq;
*/


/*
int n,r;
int T=0;
struct Node{
    double left,right;
};
Node nodes[1005];
struct rule{
    bool operator()(const Node &n1,const Node &n2){
        return n1.left<n2.left;
    }
};
int solve(){
    sort(nodes,nodes+n,rule());
    int ans=1;
	double now=nodes[0].right;
	for(int i=1;i<n;i++){
		if(nodes[i].left<=now) now=min(now,nodes[i].right);
		else{
			ans++;
			now=nodes[i].right;
		}
	}
	return ans;
}
*/


/*
typedef struct SugarBox{
	int v,w;
	double v_w;
};
struct Rule2{
	bool operator() (const SugarBox &a1,const SugarBox &a2){
		return a1.v_w>a2.v_w;
	}
};
SugarBox s[105];
*/

/*
int k,w,s;
typedef struct Node{
	int w,v,index;
	double v_w;
};
struct Rule1{
	bool operator ()(const Node &a1,const Node &a2){
		return a1.v_w>a2.v_w;
	}
};
Node n[105]; 
*/

int main(){
	
	//1797:金银岛
	/*
	cin>>k;
	while(k--){
		cin>>w;
		cin>>s;	
		for(int i=0;i<s;i++){
			cin>>n[i].w>>n[i].v;
			n[i].index=i;
			n[i].v_w=n[i].v*1.000/n[i].w;
		}
		sort(n,n+s,Rule1());
		int totalW=0;
		double totalV=0;
		for(int i=0;i<s;i++){
			if (totalW>=w){
				break;
			}
			if(n[i].w+totalW<=w){
				totalV+=n[i].v;
				totalW+=n[i].w;
			}else{				
				totalV+=n[i].v_w*(w-totalW);
				totalW=w;
			}
		}
		printf("%.2lf\n",totalV);
	}
	*/
	
	
	//4110:圣诞老人的礼物-Santa Clau’s Gifts
	/*
	int n,w;
	cin>>n>>w;
	for(int i=0;i<n;i++){
		cin>>s[i].v>>s[i].w;
		s[i].v_w=1.00*s[i].v/s[i].w;
	}
	sort(s,s+n,Rule2());
	int totalW=0;
	double totalV=0;
	for(int i=0;i<n;i++){
		if(totalW+s[i].w<=w){
			totalV+=s[i].v*1.0;
			totalW+=s[i].w;
		}else{
			totalV+=s[i].v_w*(w-totalW);
			break;
		}
	} 
	printf("%.1lf",totalV);
	*/
	
	//3468:电池的寿命
	/*
	int n;
	while(cin>>n){
		int sum=0;
		int x,max;
		max=-1;
		for(int i=0;i<n;i++){
			cin>>x;
			sum+=x;
			if(x>max){
				max=x;
			}
		}
		int y=sum-max;
		if(max>y){
			printf("%.1lf\n",1.0*y);
		}else{
			printf("%.1lf\n",1.0*sum/2.0);
		}
	}
	*/
	
	//1328:Radar Installation
	/*
	while (true){
		scanf("%d%d",&n,&r);
        if(n==0&&r==0) return 0;
        T++;
        bool flag=true;
        for (int i = 0; i < n; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            if (y>r){
            	flag=false;
			}
                
            nodes[i].left=x-sqrt(r*r-y*y);
            nodes[i].right=x+sqrt(r*r-y*y);
        }
        if (flag)
            printf("Case %d: %d\n",T,solve());
        else
            printf("Case %d: -1\n",T);

    }
    */
    
    
    //4144:畜栏保留问题
    /*
    int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>cows[i].start>>cows[i].end;
		cows[i].No=i;
	}
	sort(cows,cows+n);
	
	int totalN=0;
	for(int i=0;i<n;i++){
		if(pq.empty()){
			++totalN;
			pq.push(Stall(cows[i].end,totalN));
			pos[cows[i].No]=totalN;
		}else{
			Stall st=pq.top();
			if(cows[i].start>st.end){
				pq.pop();
				pq.push(Stall(cows[i].end,st.No));
				pos[cows[i].No]=st.No;
			}else{
				++totalN;
				pq.push(Stall(cows[i].end,totalN));
				pos[cows[i].No]=totalN;
			}
		}
	}
	cout<<totalN<<endl;
	for(int i=0;i<n;i++){
		cout<<pos[i]<<endl;
	}
	*/
	
	//1042:Gone Fishing
	/*
	int ans,now;
	cin>>n;
	while(n!=0){
		cin>>t;
		t*=12;		
		for(int i=0;i<n;i++)
		cin>>a[i].f;
		for(int i=0;i<n;i++){
			cin>>a[i].d;
			a[i].id=i;
			best[i]=0;
		}
		dis[0]=0;
		for(int i=1;i<n;i++){
			cin>>dis[i];
			dis[i]+=dis[i-1];
		}
		
		ans=-1;
		for(int i=0;i<n;i++){
			now=0;			
			while(!pq.empty()) pq.pop();
			for(int j=0;j<=i;j++){
				pq.push(a[j]);
			}
			for(int j=0;j<n;j++){
				temp[j]=0;
			}
			
			int tt=t-dis[i];
			while(tt>0){
				Node node=pq.top();
				pq.pop();
				temp[node.id]++;
				now+=node.f;
				tt--;
				node.f-=node.d;
				if(node.f<0) node.f=0;
				pq.push(node);				
			}
			
			if(now>ans){
				ans=now;
				for(int j=0;j<n;j++){
					best[j]=temp[j];
				}
			}
		}
		cout<<best[0]*5;
		for(int i=1;i<n;i++){
			cout<<", "<<best[i]*5;
		}
		cout<<endl;
		cout<<"Number of fish expected: "<<ans<<endl;
		
		cin>>n;
		if(n>0) cout<<endl;	
	}
	*/
	
	
	//4151:电影节
	/*
	int n;
	while(cin>>n){
		if(n==0){
			return 0;
		}
		for(int i=0;i<n;i++){
			cin>>node[i].start>>node[i].end;
		}
		sort(node,node+n);
		int totalN=1;
		int totalEnd=node[0].end;
		for(int i=1;i<n;i++){
			if(node[i].start>=totalEnd){
				totalN++;
				totalEnd=node[i].end;
			}
		}
		cout<<totalN<<endl;		
	}
	*/
	
	//2287:Tian Ji -- The Horse Racing
	/*
	while(cin>>n){
		if(n==0)
		return 0;
		
		for(int i=0;i<n;i++)
		cin>>a[i];
		for(int i=0;i<n;i++)
		cin>>b[i];
		
		sort(a,a+n);
		sort(b,b+n);
		
		money=0;
		l1=l2=0;
		r1=r2=n-1;
		while(l1<=r1){
			if(a[r1]>b[r2]){
				r1--;
				r2--;
				money+=200;
			}else if(a[r1]<b[r2]){
				l1++;
				r2--;
				money-=200;
			}else{
				if(a[l1]>b[l2]){
					l1++;
					l2++;
					money+=200;
				}else{
					if(a[l1]<b[r2]) money-=200;
					l1++;
					r2--;
				}
			}
		}
		cout<<money<<endl;
		
	}
	*/
	
	/*
	//1455:An Easy Problem
	int n;
	while(cin>>n){
		if(n==0) return 0;
		int temp=numof1(n);
		int i;
		for(i=n+1;numof1(i)!=temp;i++){}
		cout<<i<<endl;
	}
	*/
	/*
	//2407:书架	
	cin>>N>>B;
	for(int i=0;i<N;i++){
		cin>>H[i];
		prq.push(H[i]);
	}
	while(S<B){
		int temp=prq.top();prq.pop();
		S+=temp;
		res++;
	}
	cout<<res<<endl;
	*/
	return 0;
}
